import jdk.internal.org.objectweb.asm.util.CheckAnnotationAdapter;

public class Test {
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1, MySingleList.ListNode list2) {

        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmpH = newHead;

        while(list1 != null && list2 != null) {
            //1.list2.val < list1.val
            if(list2.val < list1.val) {
                tmpH.next = list2;
                tmpH = tmpH.next;

                list2 = list2.next;

            }else {
                tmpH.next = list1;
                tmpH = tmpH.next;
                list1 = list1.next;
            }
        }
        if(list1 != null) {
            tmpH.next = list1;
        }
        if(list2 != null) {
            tmpH.next = list2;
        }
        return newHead.next;

    }
    //力扣题目：相交链表
    public MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        //判断两个链表是否为空，为空就返回null
        if(headA == null || headB == null) {
            return null;
        }
        //1.分别求两个链表的长度
        MySingleList.ListNode plong = headA;//假设A是最长的
        MySingleList.ListNode pshort = headB;
        int lenA = 0;
        int lenB = 0;
        while(plong != null) {
            lenA++;
            plong = plong.next;
        }

        while(pshort != null) {
            lenB++;
            pshort = pshort.next;
        }
        plong = headA;
        pshort = headB;
        //2.求差值步
        int len = lenA - lenB;
        if(len < 0) {
            plong = headB;
            pshort = headA;
            len = lenB - lenA;
        }
        //plong一定指向最长的链表
        //3.那个链表最长就走len步
        while(len != 0) {
            plong = plong.next;
            len--;
        }
        //4.两个链表一起走，如果两个链表不相交最终遍历完链表，plong和pshort最终会相等都等于null
        while(plong != pshort) {
            plong = plong.next;
            pshort = pshort.next;
        }

        return plong;



    }

    public static void main(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(34);
        mySingleList1.addLast(21);

        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(12);
        mySingleList2.addLast(31);
        mySingleList2.addLast(75);

        MySingleList.ListNode ret = mergeTwoLists(mySingleList1.head,mySingleList2.head);

        mySingleList1.show(ret);

    }
    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addFirst(12);
        mySingleList.addFirst(34);
        mySingleList.addFirst(21);
        //鏈表倒数第k个节点
        MySingleList.ListNode ret = mySingleList.getKthFromEnd(1);
        System.out.println(ret.val);
        //清空测试
        /*mySingleList.clear();
        mySingleList.show();*/
    }

}
